class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}
export {}
/**
 * 二叉搜索树转为链表
 * @param root 
 */
const convertBiNode = (root: TreeNode | null): TreeNode | null => {
    if (root === null) return null

    const dummyHead = new TreeNode(0);
    let head = dummyHead;

    const inorder = (root: TreeNode | null) => {
        // 左孩子为空, 返回该节点
        if (root === null) return;

        // 遍历左边
        inorder(root.left);

        // head的左右就是改变right指向
        head.right = root;
        head = root;
        root.left = null

        // 遍历右子树
        inorder(root.right)

    }

    inorder(root)

    return dummyHead.right;
};

// 非递归
const convertBiNode2 = (root: TreeNode | null): TreeNode | null => {
    if (root === null) return null

    // 直到节点的前驱节点, 让前驱节点指向自己

    /**
     * 获取n的前驱节点
     * @param n 
     */
    const getAced = (n: TreeNode) => {
        let left = n.left;

        // 一直往左边的右边找
        while (left !== null && left.right !== null && left.right !== n) {
            left = left.right
        }

        return left;
    }

    /**
     * 获取节点n的后继节点
     * @param n 
     */
    const getSucced = (n: TreeNode) => {
        let right = n.right;
        while (right !== null && right.left !== null) {
            right = right.left;
        }
        return right;
    }

    let p = root,
        lock = false,
        ans = root;
    while (p !== null) {
        if (p.left !== null) {
            // 左子节点不为空

            // 找到前驱节点
            const aced = getAced(p)!;

            // 前驱节点的right指向自己
            if (aced.right === null) {
                aced.right = p;
                let tmp = p.left;
                p.left = null // 将p.left置空
                p = tmp
            } else if (aced.right === p) {
                // 第二次找到该节点
                // p = p.right!;
                // 找到p的后继节点
                const succed = getSucced(p);
                let tmp = p.right;
                p.right = succed;
                p = tmp!
            }
        } else {
            // 左子节点为空, 指向右节点
            // p = p.right!;
            if (!lock) {
                lock = true;
                ans = p
            }
            const succed = getSucced(p);
            let tmp = p.right;
            p.right = succed
            p = tmp!
        }
    }
    return ans;
};